package com.hanxiaozhang.no10leetcode.link;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈合并两个有序list〉
 * 实例:
 * 输入: 1->2->4, 1->3->4
 * 输出: 1->1->2->3->4->4
 * <p>
 * 思路：方法1 ，它参考两个数组的合并 twoArrayMergeSort （背）
 * 1. 设置一个傀儡头节点，省去很多判空的操作，结果返回时puppet.next
 * 2. 循环比较两个链表元素大小
 * -- 当前节点的后继赋值
 * -- node1/node2后移一位
 * -- 当前节点后移一位
 * 3. 判断两个链表那个不为空，当前节点的后继赋值
 * 4. 返回傀儡头节点的后继节点
 *
 *
 * @author hanxinghua
 * @create 2024/1/31
 * @since 1.0.0
 */
public class No21MergeTwoSortedLists {


    public static void main(String[] args) {

        int[] nums1 = {1, 2, 4};
        int[] nums2 = {1, 3, 4};

        System.out.println(Arrays.toString(twoArrayMergeSort(nums1, nums2)));

        Node<Integer> node1 = new Node<>(1);
        node1.next = new Node(2);
        node1.next.next = new Node(4);

        Node<Integer> node2 = new Node(1);
        node2.next = new Node(3);
        node2.next.next = new Node(4);


//        Node head1 = method1(node1, node2);
//        LinkUtil.whileNode(head1);

        Node head2 = method2(node1, node2);
        LinkUtil.printLink(head2);


    }


    /**
     * 方法1
     *
     * @param node1
     * @param node2
     * @return
     */
    public static Node method1(Node<Integer> node1, Node<Integer> node2) {
        // 设置一个傀儡头节点，省去很多判空的操作，结果返回时puppet.next
        Node dummyHead = new Node(-1);
        // 当前节点
        Node cur = dummyHead;

        while (node1 != null && node2 != null) {
            if (node1.data < node2.data) {
                // 当前节点的后继 赋值成 node1
                cur.next = node1;
                // node1后移一位
                node1 = node1.next;
            } else {
                // 当前节点的后继 赋值成 node2
                cur.next = node2;
                // node2后移一位
                node2 = node2.next;
            }
            // 当前节点后移一位
            cur = cur.next;
        }

        if (node1 != null) {
            cur.next = node1;
        } else {
            cur.next = node2;
        }
        return dummyHead.next;
    }


    /**
     * 方法2
     * <p>
     * 简单递归调用即可，相当于是归并排序最后的合并步骤
     *
     * @param node1
     * @param node2
     * @return
     */
    public static Node method2(Node<Integer> node1, Node<Integer> node2) {
        if (node1 == null) {
            return node2;
        }
        if (node2 == null) {
            return node1;
        }
        if (node1.data < node2.data) {
            node1.next = method2(node1.next, node2);
            return node1;
        } else {
            node2.next = method2(node1, node2.next);
            return node2;
        }
    }


    /**
     * 拓展：两个数组合并排序
     *
     * @param nums1
     * @param nums2
     * @return
     */
    private static int[] twoArrayMergeSort(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length + nums2.length];

        int index1 = 0, index2 = 0, index = 0;
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] < nums2[index2]) {
                nums[index++] = nums1[index1++];
            } else {
                nums[index++] = nums2[index2++];
            }
        }
        if (index1 < nums1.length) {
            nums[index++] = nums1[index1++];
        }
        if (index2 < nums2.length) {
            nums[index++] = nums2[index2];
        }
        return nums;
    }


}
